package com.gxc.tree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 */
public class LowestCommonAncestorNode {

    public static void main(String[] args) {
        TreeBean one = new TreeBean(1);
        TreeBean two = new TreeBean(2);
        TreeBean three = new TreeBean(3);
        TreeBean four = new TreeBean(4);
        TreeBean five = new TreeBean(5);
        TreeBean six = new TreeBean(6);
        TreeBean seven = new TreeBean(7);
        TreeBean eight = new TreeBean(8);

        one.left = two;
        one.right = three;

        two.left = four;
        two.right = five;

        three.left = six;
        three.right = seven;

        four.left = eight;

        TreeBean node = extraSpaceLca(one, eight, five);
        System.out.println(node.value);

        node = noXxtraSpaceLca(one, eight, five);
        System.out.println(node.value);
    }

    /**
     * 没有额外空间，递归查询最低公共祖先节点
     * @param head
     * @param node1
     * @param node2
     * @return
     */
    private static TreeBean noXxtraSpaceLca(TreeBean head, TreeBean node1, TreeBean node2) {
        if (head == null || head == node1 || head==node2) return head;

        TreeBean leftNode = noXxtraSpaceLca(head.left, node1, node2);
        TreeBean rightNode = noXxtraSpaceLca(head.right, node1, node2);

        if (leftNode!= null && rightNode!=null) return head;
        return leftNode!=null?leftNode:rightNode;
    }

    /**
     * 使用额外空间记录node1，node2所有的父级node
     * @param head
     * @param node1
     * @param node2
     * @return
     */
    private static TreeBean extraSpaceLca(TreeBean head, TreeBean node1, TreeBean node2) {
        Map<TreeBean, TreeBean> fatherMap = new HashMap<>();
        fatherMap.put(head, head);
        putFather(head, fatherMap);

        Set<TreeBean> node1Father = new HashSet<>();
        TreeBean cur = node1;
        while (cur != fatherMap.get(cur)) {
            node1Father.add(cur);
            cur = fatherMap.get(cur);
        }
        node1Father.add(head);

        cur = node2;
        while (cur!=fatherMap.get(cur)) {
            if (node1Father.contains(cur)) return cur;
            cur = fatherMap.get(cur);
        }
        return head;
    }

    /**
     *
     * @param head
     * @param fatherMap
     */
    private static void putFather(TreeBean head, Map<TreeBean, TreeBean> fatherMap) {
        if (head == null) return;
        fatherMap.put(head.left, head);
        fatherMap.put(head.right, head);
        putFather(head.left, fatherMap);
        putFather(head.right, fatherMap);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }

}
